#include "ad_construct.h"
#include <cstdio>
#include <cstring>
#include <algorithm>

// TODO: CHECK THIS STUFF
const bool bad_length(const int len, const int alph_size){
  if (len <= alph_size || len==2*alph_size) return false;
  if (len%alph_size==0 && len>=5*alph_size) return false;
  if (alph_size & 1){
    int z = len - (alph_size - 1)*(alph_size + 1) / 2;
    if (z < 0) return true;
    int d = z / alph_size;
    int r = z % alph_size;
    if (z - d * alph_size <= r) return false;
    if ((d+1) * alph_size - z <= r+1) return false;
  }
  else{
    int z = len - (alph_size - 1)*(alph_size + 2) / 2;
    if (z < 0) return true;
    int d = z / alph_size;
    int r = z % alph_size;
    if (z - d * alph_size <= r+1) return false;
    if ((d+1) * alph_size - z <= r+1) return false;
  }
  return true;
}

inline int get_length(int plen, input_data & INPUT){
  return (2 * plen * INPUT.beta.num + INPUT.beta.p + 2 * INPUT.beta.denum - 1) / (2 * INPUT.beta.denum);
}

int handle_root(const char* cword, int clen, bool trie_enough, dfa * DFA, input_data & INPUT){
  int alph_size = INPUT.ALPH_SIZE;
  // For big alphabets and k/(k-1)+ langs not all lengths can occur
  if (alph_size >= 6 && INPUT.beta == ext_rational(alph_size, alph_size-1, 1) && bad_length(clen, alph_size)){
    // TODO: SEEMS STRANGE
    return 0;
  }
  
  char thword[MAX_WORD_LENGTH + 1];
  char maxlet = 'a';
  int i;
  for (i=0; i<clen; i++){
    thword[i] = cword[i];
    if (thword[i] > maxlet){
      maxlet = thword[i];
    }
  }
  int blen = clen, cpos = 0;
  int nlen = get_length(clen, INPUT);
  while (blen < nlen){
    thword[blen++] = thword[cpos];
    cpos++;
    if (cpos >= clen) cpos = 0;
  }
  thword[blen] = 0;

  if (blen > MAX_WORD_LENGTH){
    INPUT.dump("Too small maximal length of forbidden word!\n");
    exit(1);
  }
  for (i=clen+1; i<blen; i++){
    if (DFA->bad_suffix_trie(thword, i, -1)){
      return i;
    }
  }
  if (DFA->bad_suffix_trie(thword+1, blen-1, -1) || DFA->bad_suffix_trie(thword, blen, 1)){
    return blen;
  }

  if (!trie_enough){
    int bad_pref_num = has_bad_prefix_dumb(thword, blen-1, clen, INPUT);
    if (bad_pref_num > 0) return bad_pref_num + 1;
    if (has_bad_prefix_dumb(thword+1, blen-1, blen-2, INPUT)){
      return blen;
    }
  }

  DFA->add_word(thword);
  return 0;
}

int max_trie_height;
int max_root_length;

int has_bad_prefix_dumb(const char* cword, int clen, int slen, input_data & INPUT){
  int pos, rlen, i, xlen;
  for (pos=slen; pos<clen; pos++){
    for (rlen=max_root_length + 1; INPUT.beta.num * rlen < INPUT.beta.denum * (pos+1); rlen++){
      xlen = get_length(rlen, INPUT);
      for (i=rlen; i<xlen; i++){
        if (cword[pos-i] != cword[pos-i+rlen]) break;
      }
      if (i == xlen) return pos;
    }
  }
  return 0;
}

void run_dfs(char * cword, int clen, char maxlet, dfa * DFA, input_data & INPUT){
  bool trie_enough = false;
  // TODO : CHECK THIS STUFF!
  if (INPUT.beta < ext_rational(2,1,0)){
    if (max_trie_height >= clen-1) trie_enough = true;
    else{
      int cleft = 2 * clen - get_length(clen, INPUT);
      if (INPUT.beta <= ext_rational(4,3,1) && max_root_length >= cleft) trie_enough = true;
      else if (INPUT.beta <= ext_rational(5,4,1) && max_root_length >= cleft-1) trie_enough = true;
    }
  }

  int fbad = handle_root(cword, clen, trie_enough, DFA, INPUT);
  char dont_put_a = (fbad == clen+1);
  
  if (clen == INPUT.ROOT_LENGTH){
    cword[clen] = 0;
    return;
  }
  for (char ch = 'a'+dont_put_a; ch<=maxlet; ch++){
    cword[clen] = ch;
    cword[clen+1] = 0;
    bool ok = !DFA->bad_suffix_trie(cword, clen+1, -1);
    if (max_trie_height < clen+1){
      ok &= (has_bad_prefix_dumb(cword, clen+1, clen, INPUT) == 0);
    }
    if (ok){
      run_dfs(cword, clen+1, maxlet, DFA, INPUT);
    }
  }
  if (maxlet-'a'+1 < INPUT.ALPH_SIZE){
    cword[clen] = maxlet+1;
    cword[clen+1] = 0;
    run_dfs(cword, clen+1, maxlet+1, DFA, INPUT);
  }
}

i64 construct_antidictionary(grate_config & CONFIG, input_data & INPUT, words_queue * WORDS_QUEUE, dfa * DFA){
  i64 max_words_queue_size = 0;
  i64 marker_pos;
  int DEPTH = CONFIG.DFS_DEPTH;
  if (DEPTH > INPUT.ROOT_LENGTH - 2){
    DEPTH = INPUT.ROOT_LENGTH - 2;
  }
  max_trie_height = 0;
  max_root_length = 0;
  bool start_dfs = false;
  i64 prev_words_queue_size = 1;

  WORDS_QUEUE->push_marker(marker_pos); // sets marker_pos to 0
  WORDS_QUEUE->push_symbol('a');

  int i;
  int clen = 0;
  char bad_word[MAX_WORD_LENGTH + 1];
  char dont_put_a;

  while (! WORDS_QUEUE->is_empty()){
    if (WORDS_QUEUE->is_index(marker_pos)){
      if ((start_dfs == false) && (clen < INPUT.ROOT_LENGTH - DEPTH)){
        int nlen = get_length(clen, INPUT);
        if (nlen > max_trie_height){
          max_trie_height = nlen;
        }
        max_root_length = clen;
        clen++;
        double coef = max_words_queue_size / (double)prev_words_queue_size;
        i64 new_words_queue_size = (i64)(max_words_queue_size * coef + 10);
        if (WORDS_QUEUE->long_mask) new_words_queue_size >>= 1;
        else new_words_queue_size >>= 2;
        if (new_words_queue_size >= WORDS_QUEUE->size){
          start_dfs = true;
        }
        prev_words_queue_size = max_words_queue_size;
        WORDS_QUEUE->push_marker(marker_pos);
        WORDS_QUEUE->pop_symbol();
        continue;
      }
      else break;
    }
    
    // there is a word in the queue starting at qbeg with (length = clen)
    char maxlet = 'a';
    for (i=0; i<clen; i++){
      bad_word[i] = WORDS_QUEUE->pop_symbol() + 'a';
      if (bad_word[i] > maxlet){
        maxlet = bad_word[i];
      }
    }

    int fbad = handle_root(bad_word, clen, true, DFA, INPUT);
    dont_put_a = (fbad == clen+1);

    if (clen < INPUT.ROOT_LENGTH){
      char ch;
      for (ch='a'+dont_put_a; ch<=maxlet; ch++){
        bad_word[clen] = ch;
        bad_word[clen+1] = 0;
        if (!DFA->bad_suffix_trie(bad_word, clen+1, -1)){
          if ((start_dfs == false) && (clen < INPUT.ROOT_LENGTH - DEPTH - 1)){
            if (!WORDS_QUEUE->push_word(bad_word)){
              INPUT.dump("ERROR! Insufficient words queue size!\n");
              exit(1);              
            }
          }
          else run_dfs(bad_word, clen+1, maxlet, DFA, INPUT);
        }
      }
      if (maxlet-'a'+1 < INPUT.ALPH_SIZE){
        bad_word[clen] = maxlet+1;
        bad_word[clen+1] = 0;
        if ((start_dfs == false) && (clen < INPUT.ROOT_LENGTH - DEPTH - 1)){
          if (!WORDS_QUEUE->push_word(bad_word)){
            INPUT.dump("ERROR! Insufficient words queue size!\n");
            exit(1);              
          }
        }
        else run_dfs(bad_word, clen+1, maxlet+1, DFA, INPUT);
      }
    }

    i64 cwqsz = WORDS_QUEUE->get_number_of_letters();
    if (cwqsz > max_words_queue_size){
      max_words_queue_size = cwqsz;
    }
  }
  delete WORDS_QUEUE;

  return max_words_queue_size;
}
